Savitch's theorem #complexity_theory Theorem For any space-constructible S:ℕ→ℕS : \mathbb{N} \to \mathbb{N} with S(n)≥lognS(n) \geq \log n, 𝐍𝐒𝐏𝐀𝐂𝐄(S(n))⊆𝐒𝐏𝐀𝐂𝐄(S(n)2)\mathbf{NSPACE}(S(n)) \subseteq \mathbf{SPACE}(S(n)^2). (NSPACE, SPACE) See also PSPACE-completeness of TBQF References S. Arora, B. Barak. Computational Complexity: A Modern Approach, Cambridge University Press, 2009, p. 86.